|
In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels. The algorithm chooses an arrangement such that an element that comes after another in the order is assigned to a lower level, and such that each level has a number of elements that does not exceed a fixed width bound . When , it uses the minimum possible number of distinct levels,〔 and in general it uses at most times as many levels as necessary.〔〔 ==Problem statement and applications== In the version of the job shop scheduling problem solved by the Coffman–Graham algorithm, one is given a set of jobs , together with a system of precedence constraints requiring that job be completed before job begins. Each job is assumed to take unit time to complete. The scheduling task is to assign each of these jobs to time slots on a system of identical processors, minimizing the makespan of the assignment (the time from the beginning of the first job until the completion of the final job). Abstractly, the precedence constraints define a partial order on the jobs, so the problem can be rephrased as one of assigning the elements of this partial order to levels (time slots) in such a way that each time slot has at most as many jobs as processors (at most elements per level), respecting the precedence constraints. This application was the original motivation for Coffman and Graham to develop their algorithm.〔.〕〔.〕 In the layered graph drawing framework outlined by 〔.〕 and implemented in systems such as Microsoft Automatic Graph Layout, the input is a directed graph, and a drawing of a graph is constructed in several stages:〔〔. Bastert and Matuszewski also include a description of the Coffman–Graham algorithm; however, they omit the transitive reduction stage of the algorithm.〕 #A feedback arc set is chosen, and the edges of this set reversed, in order to convert the input into a directed acyclic graph. #The vertices of the graph are given integer -coordinates in such a way that, for each edge, the starting vertex of the edge has a higher coordinate than the ending vertex, with at most vertices sharing the same -coordinate. #Dummy vertices are introduced within each edge so that the subdivided edges all connect pairs of vertices that are in adjacent levels of the drawing. #Within each group of vertices with the same -coordinate, the vertices are permuted in order to minimize the number of crossings in the resulting drawing, and the vertices are assigned -coordinates consistently with this permutation. #The vertices and edges of the graph are drawn with the coordinates assigned to them. In this framework, the -coordinate assignment again involves grouping elements of a partially ordered set (the vertices of the graph, with the reachability ordering on the vertex set) into layers (sets of vertices with the same -coordinate), which is the problem solved by the Coffman–Graham algorithm.〔.〕 Although there exist alternative approaches than the Coffman–Graham algorithm to the layering step, these alternatives in general are either not able to incorporate a bound on the maximum width of a level or rely on complex integer programming procedures.〔.〕 More abstractly, both of these problems can be formalized as a problem in which the input consists of a partially ordered set and an integer . The desired output is an assignment of integer level numbers to the elements of the partially ordered set such that, if is an ordered pair of related elements of the partial order, the number assigned to is smaller than the number assigned to , such that at most elements are assigned the same number as each other, and minimizing the difference between the smallest and the largest assigned numbers. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Coffman–Graham algorithm」の詳細全文を読む スポンサード リンク
|